Divide Two Integers || Find Minimum in Rotated Sorted Array II

发表于

Divide Two Integers

Question

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

Analysis

  • 事先确定结果的正负号，操作过程中保证除数与被除数都为正
  • 由于无法使用乘法，所以最初想法为被除数不断地减去被除数，直到值=0，减去被除数的次数即结果
  • 对被除数进行位操作，左移k位相当于divisor的2^k倍，首先减去最大的k值下的divisor
  • shift++操作后的结果需-1是实际的结果
  • dividend - divisor移位后的结果，res + 1移位后的结果

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public int divide(int dividend, int divisor) {
        boolean isNeg=(dividend>0&&divisor<0)||(dividend<0&&divisor>0);
        if(dividend==0)
            return 0;
        if(divisor==0)
            return -1;
        if (dividend == Integer.MIN_VALUE && divisor == -1)
            return Integer.MAX_VALUE;
        long up=Math.abs((long)dividend);
        long down=Math.abs((long)divisor);
        int res=0;
        
        while(up>=down){
            int shift=0;
            while(up>=(down<<shift)){
                shift++;
            }
            res+=1<<(shift-1);
            up-=down<<(shift-1);
        }
        
        if(isNeg)   return -res;
        return res;
    }
}

Find Minimum in Rotated Sorted Array II

Question

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Analysis

九章算法

同样当A[mid] = A[end]时，无法判断min究竟在左边还是右边。

3 1 2 3 3 3 3
3 3 3 3 1 2 3

但可以肯定的是可以排除A[end]：因为即使min = A[end]，由于A[end] = A[mid]，排除A[end]并没有让min丢失。所以增加的条件是：

A[mid] = A[end]：搜索A[start : end-1]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int findMin(int[] nums) {
        int begin=0;
        int end=nums.length-1;
        while(begin<end){
            if(nums[begin]<nums[end])
                return nums[begin];
            int mid=begin/2+end/2;
            if(nums[mid]>=nums[begin])
                begin=mid+1;
            else
                end=mid;
        }
        return nums[begin];
    }
}